package com.duoduo.demo.math;

import java.util.Arrays;

/**
 * 从n个数里取出m个数的排列或组合算法实现
 * @author chengesheng
 * @date 2016年9月28日 下午3:18:34
 */
public class MathTest {

	public static void main(String[] args) {
		// select(2);
		arrangementSelect(new String[] {
				"1", "2", "3", "4"
		}, 2);
		combinationSelect(new String[] {
				"1", "2", "3", "4", "5"
		}, 3);
	}

	private static char[] a = {
			'a', 'b', 'c'
	};

	private static void select(int k) {
		char[] result = new char[k];
		subselect(0, 1, result, k);
	}

	private static void subselect(int head, int index, char[] r, int k) {
		for (int i = head; i < a.length + index - k; i++) {
			if (index < k) {
				r[index - 1] = a[i];
				System.out.println("i=" + (i) + ";index=" + (index));
				subselect(i + 1, index + 1, r, k);
			} else if (index == k) {
				r[index - 1] = a[i];
				System.out.println(";i=" + (i) + ";index=" + (index) + ";index==k:" + (index == k));
				System.out.print(i + "===");
				System.out.println(r);
				subselect(i + 1, index + 1, r, k);
			} else {
				System.out.println("++");
				return;// 返回到何处？奇怪
			}
		}
	}

	/**
	 * 排列选择（从列表中选择n个排列）
	 * @param dataArray 待选列表
	 * @param n 选择个数
	 */
	public static void arrangementSelect(String[] dataArray, int n) {
		System.out.println(String.format("A(%d, %d) = %d", dataArray.length, n, arrangement(dataArray.length, n)));
		arrangementSelect(dataArray, new String[n], 0);
	}

	/**
	 * 排列选择
	 * @param dataArray 待选列表
	 * @param resultArray 前面（resultIndex-1）个的排列结果
	 * @param resultIndex 选择索引，从0开始
	 */
	private static void arrangementSelect(String[] dataArray, String[] resultArray, int resultIndex) {
		int resultLen = resultArray.length;
		if (resultIndex >= resultLen) { // 全部选择完时，输出排列结果
			System.out.println(Arrays.asList(resultArray));
			return;
		}

		// 递归选择下一个
		for (int i = 0; i < dataArray.length; i++) {
			String[] subArray = Arrays.copyOfRange(resultArray, 0, resultIndex); // 获取已排列数组
			if (!Arrays.asList(subArray).contains(dataArray[i])) { // 排列结果不存在该项，才可选择
				resultArray[resultIndex] = dataArray[i];
				arrangementSelect(dataArray, resultArray, resultIndex + 1);
			}
		}
	}

	/**
	 * 组合选择（从列表中选择n个组合）
	 * @param dataArray 待选列表
	 * @param n 选择个数
	 */
	public static void combinationSelect(String[] dataArray, int n) {
		System.out.println(String.format("C(%d, %d) = %d", dataArray.length, n, combination(dataArray.length, n)));
		combinationSelect(dataArray, 0, new String[n], 0);
	}

	/**
	 * 组合选择
	 * @param dataArray 待选列表
	 * @param dataIndex 待选开始索引
	 * @param resultArray 前面（resultIndex-1）个的组合结果
	 * @param resultIndex 选择索引，从0开始
	 */
	private static void combinationSelect(String[] dataArray, int dataIndex, String[] resultArray, int resultIndex) {
		int resultLen = resultArray.length;
		int resultCount = resultIndex + 1;
		if (resultCount > resultLen) { // 全部选择完时，输出组合结果
			System.out.println(Arrays.asList(resultArray));
			return;
		}

		// 递归选择下一个
		for (int i = dataIndex; i < dataArray.length + resultCount - resultLen; i++) {
			resultArray[resultIndex] = dataArray[i];
			combinationSelect(dataArray, i + 1, resultArray, resultIndex + 1);
		}
	}

	/**
	 * 计算阶乘数，即n! = n * (n-1) * ... * 2 * 1
	 * @param n
	 * @return
	 */
	public static long factorial(int n) {
		return (n > 1) ? n * factorial(n - 1) : 1;
	}

	/**
	 * 计算排列数，即A(n, m) = n!/(n-m)!
	 * @param n
	 * @param m
	 * @return
	 */
	public static long arrangement(int n, int m) {
		return (n >= m) ? factorial(n) / factorial(n - m) : 0;
	}

	/**
	 * 计算组合数，即C(n, m) = n!/((n-m)! * m!)
	 * @param n
	 * @param m
	 * @return
	 */
	public static long combination(int n, int m) {
		return (n >= m) ? factorial(n) / factorial(n - m) / factorial(m) : 0;
	}
}
